import java.util.Arrays;
/**
 * 这是 LeetCode 1326. 灌溉花园的最少水龙头数目
 * https://leetcode.cn/problems/minimum-number-of-taps-to-open-to-water-a-garden
 */
class MinimumNumberOfTapsToOpenToWaterAGarden {
    /**
     * 方法：贪心算法
     * 
     * 功能：计算浇灌整个花园所需的最少水龙头数量
     * 
     * 实现逻辑：
     * 1. 首先计算每个位置能到达的最远右端点:
     *    - 对于每个水龙头i，计算其覆盖范围[i-ranges[i], i+ranges[i]]
     *    - 对于范围内的每个起点，更新其能到达的最远右端点
     * 2. 使用贪心策略遍历花园:
     *    - 维护当前能到达的右端点curRight和下一步能到达的最远右端点nextRight
     *    - 当到达curRight时，必须选择一个新的水龙头，更新curRight为nextRight
     *    - 如果无法继续前进(i == nextRight)，返回-1
     * 3. 返回使用的水龙头数量
     * 
     * 时间复杂度：O(n)，其中n为花园长度，需要遍历一次数组计算右端点，再遍历一次选择水龙头
     * 
     * 空间复杂度：O(n)，需要一个数组存储每个位置能到达的最远右端点
     */
    public int minTaps2(int n, int[] ranges) {
        int[] rightMost = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int r = ranges[i];
            // 这样写可以在 i>r 时少写一个 max
            // 凭借这个优化，恭喜你超越了 100% 的用户
            // 说「超越」是因为原来的最快是 2ms，现在优化后是 1ms
            if (i > r) rightMost[i - r] = i + r; // 由于 i 在不断变大，对于 i-r 来说，i+r 必然是它目前的最大值
            else rightMost[0] = Math.max(rightMost[0], i + r);
        }

        int ans = 0;
        int curRight = 0; // 已建造的桥的右端点
        int nextRight = 0; // 下一座桥的右端点的最大值
        for (int i = 0; i < n; i++) { // 如果走到 n-1 时没有返回 -1，那么必然可以到达 n
            nextRight = Math.max(nextRight, rightMost[i]);
            if (i == curRight) { // 到达已建造的桥的右端点
                if (i == nextRight) return -1; // 无论怎么造桥，都无法从 i 到 i+1
                curRight = nextRight; // 造一座桥
                ans++;
            }
        }
        return ans;
    }

    public int minTaps(int n, int[] ranges) {
        int[] rightMost = new int[n+1];
        for(int i = 0; i<= n; i++){
            rightMost[i] = i;
        }
        for(int i = 0; i<= n; i++){
            int start = Math.max(0, i - ranges[i]);
            int end = Math.min(n, i + ranges[i]);
            rightMost[start] = Math.max(rightMost[start], end);
        }
        int last = 0, ret = 0, pre =0;
        for(int i = 0; i < n; i++){
            last = Math.max(last, rightMost[i]);
            if(i == last){
                return -1;
            }
            if(i == pre){
                pre = last;
                ret++;
            }
        }
        return ret;
    }

    /**
     * 方法：动态规划
     * 
     * 功能：计算浇灌整个花园所需的最少水龙头数量
     * 
     * 实现逻辑：
     * 1. 将每个水龙头的覆盖范围转换为区间[start, end]
     * 2. 按区间起点排序
     * 3. 使用dp数组记录覆盖到每个位置所需的最少水龙头数
     * 4. 遍历每个区间:
     *    - 如果起点无法到达，返回-1
     *    - 更新区间内每个位置的最少水龙头数
     * 5. 返回dp[n]作为覆盖整个花园所需的最少水龙头数
     * 
     * 时间复杂度：O(n*m)，其中n为花园长度，m为水龙头数量。需要遍历每个区间的每个位置
     * 
     * 空间复杂度：O(n)，需要一个dp数组记录每个位置的最少水龙头数
     */
    public int minTaps1(int n, int[] ranges) {
        int[][] intervals = new int[n + 1][];
        for (int i = 0; i <= n; i++) {
            int start = Math.max(0, i - ranges[i]);
            int end = Math.min(n, i + ranges[i]);
            intervals[i] = new int[]{start, end};
        }
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int[] interval : intervals) {
            int start = interval[0], end = interval[1];
            if (dp[start] == Integer.MAX_VALUE) {
                return -1;
            }
            for (int j = start; j <= end; j++) {
                dp[j] = Math.min(dp[j], dp[start] + 1);
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        MinimumNumberOfTapsToOpenToWaterAGarden solution = new MinimumNumberOfTapsToOpenToWaterAGarden();
        testMinTaps(solution);
    }

    private static void testMinTaps(MinimumNumberOfTapsToOpenToWaterAGarden solution) {
        // 测试用例1：基本测试
        int n1 = 5;
        int[] ranges1 = {3,4,1,1,0,0};
        int result1 = solution.minTaps(n1, ranges1);
        System.out.println("Test Case 1:");
        System.out.println("Expected: 1, Actual: " + result1);
        assertEquals(1, result1);

        // 测试用例2：需要多个水龙头
        int n2 = 7;
        int[] ranges2 = {1,2,1,0,2,1,0,1};
        int result2 = solution.minTaps(n2, ranges2);
        System.out.println("\nTest Case 2:");
        System.out.println("Expected: 3, Actual: " + result2);
        assertEquals(3, result2);

        // 测试用例3：无法覆盖整个花园
        int n3 = 3;
        int[] ranges3 = {0,0,0,0};
        int result3 = solution.minTaps(n3, ranges3);
        System.out.println("\nTest Case 3:");
        System.out.println("Expected: -1, Actual: " + result3);
        assertEquals(-1, result3);

        System.out.println("\nAll test cases passed!");
    }

    private static void assertEquals(int expected, int actual) {
        if (expected != actual) {
            throw new AssertionError("Expected: " + expected + ", but got: " + actual);
        }
    }
}